翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

polynomial hierarchy : ウィキペディア英語版
polynomial hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic.
==Definitions==
There are multiple equivalent definitions of the classes of the polynomial hierarchy.

:\Sigma_^ := \mbox^^ := \mbox^ = , \Pi_1^ = , and \Delta_2^ =
*), let p be a polynomial, and define
: \exists^p L := \left\^ \right) \langle x,w \rangle \in L \right. \right\},
where \langle x,w \rangle \in \^
* is some standard encoding of the pair of binary strings ''x'' and ''w'' as a single binary string. ''L'' represents a set of ordered pairs of strings, where the first string ''x'' is a member of \exists^p L, and the second string ''w'' is a "short" (|w| \leq p(|x|) ) witness testifying that ''x'' is a member of \exists^p L. In other words, x \in \exists^p L if and only if there exists a short witness ''w'' such that \langle x,w \rangle \in L . Similarly, define
: \forall^p L := \left\^ \right) \langle x,w \rangle \in L \right. \right\}
Note that De Morgan's Laws hold: \left( \exists^p L \right)^ = \forall^p L^ and \left( \forall^p L \right)^ = \exists^p L^ , where ''L''c is the complement of ''L''.
Let \mathcal be a class of languages. Extend these operators to work on whole classes of languages by the definition
:\exists^ \mathcal := \left\ \right\}
:\forall^ \mathcal := \left\ \right\}
Again, De Morgan's Laws hold: \exists^ \mathcal = \forall^ \mathcal and \forall^ \mathcal = \exists^ \mathcal , where \mathcal = \left\.
The classes NP and co-NP can be defined as = \exists^ , and = \forall^ , where P is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as
: \Sigma_0^ := \Pi_0^ :=
: \Sigma_^ := \exists^ \Pi_k^
: \Pi_^ := \forall^ \Sigma_k^
Note that = \Sigma_1^ , and = \Pi_1^ .
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
|3=An equivalent definition in terms of alternating Turing machines defines \Sigma_k^ (respectively, \Pi_k^) as the set of decision problems solvable in polynomial time on an alternating Turing machine with k alternations starting in an existential (respectively, universal) state.
}}

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「polynomial hierarchy」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.